1. Field of the Invention
The present invention relates generally to transforming one or more independent variables to one or more dependent variables where a closed-form expression for each transform is not adequately known or, if known, is not useable practically due to its complexity. More particularly, the invention relates to color imaging apparatus that employs a least squares algorithm to construct a multi-dimensional look-up table for transforming imaging information between non-linearly related color spaces.
2. Description of the Prior Art
In the following description of relevant background art, reference is made to FIGS. 1(a) and 1(b), of the accompanying drawings, which illustrate a problem associated with interpolating linearly between neighboring values of a digitally operated look-up table defining a non-linear function.
Color image reproduction systems known in the art permit an operator to edit the color and composition of an original image to form a reproduced image. For example, U.S. Pat. No. 4,500,919 discloses an image reproduction system of one type in which an electronic reader scans an original color image, which may be in the form of a transparency or a print, and converts it to an electronic image. A computer workstation and an interactive operator interface, including a video display, permits an operator to edit the image displayed. When the operator has composed a desired image on the video display, the workstation causes an output writer device to make an inked output that is intended to match the reproduced image composed on the video display.
Imaging signals, for example signals corresponding to the primaries red (R), green (G), and blue (B), serve for driving the video display and the output writer devices used in the variety of color image reproduction systems known in the art. Each output imaging device, however, may require its own set of color signals, even though each set corresponds to the same colors, in order to account for differences in the color sensitivities of the different output imaging devices. For example, with a color image reproduction system that employs a film writer as an output device, the RGB color signals that drive the video display may be different from the RGB signals that drive the film writer. Moreover, to facilitate color correction, the computer itself may store color signals in a coordinate system that is device independent and relates to the perceptually relevant dimensions such as the Munsell value, hue, and chroma; the 1976 CIE color spaces CIELAB (L* a* b*) and CIELUV (L* u* v*); etc. Accordingly, the computer workstation is required to manipulate color signals, corresponding to the various images stored, produced and displayed, in a variety of coordinate systems.
In a computational sense, color correction requires the definition of multiple complicated functions in their respective color spaces (device dependent and independent) and the ability to transform or to map a set of color imaging data between one color space and a corresponding set of imaging data in one or more other color spaces. Color correction is a computationally expensive step because the various "color spaces" or coordinate systems used are related as complicated non-linear transformations between multiple variables that in some cases are not all independent of one another.
In more recently developed commercially available color image reproduction systems, color signals have been computer processed in digital form because of the high accuracy, speed, and flexibility that digital color correction can provide. To those ends, U.S. Pat. No. 4,346,402 teaches that color correction can be carried out by means of a digitally operated look-up table, referred to generally hereinafter as a LUT, for transforming color coordinate values from one color space to another color space.
To rival analog processing in flexibility, however, digital color correction must handle large digital data sets defining non-linear transformations. It can be appreciated by those skilled in the color imaging art that a brute-force LUT implementation requiring no on-line calculation for mapping from one color space to another would be prohibitive in computer storage space because, even with modern day memory devices, the number of data storage cells cannot be increased indefinitely.
One way to reduce the storage space that a LUT requires is to reduce the amount of data used to define a given color space and to provide on-line digital processing that linearly interpolates between adjacent data points (nodes) of the LUT. A piece-wise linear interpolation procedure, however, only approximates a higher-order non-linear function of the kind descriptive of color spaces actually employed.
FIG. 1(a), for example, shows an error (.epsilon.) between the actual values of a non-linear function and corresponding linearly interpolated values; more specifically, FIG. 1(b) illustrates an error, over the interval x=0 to x=1, between actual values of the cubic function, x.sup.3, and linearly interpolated values derived from a LUT defining the cubic at equally spaced nodes x={0, 0.2, 0.4, 0.6, 0.8, 1.0}. Although the error is zero at each node, it has local maxima at points midway between adjacent nodes and is always negative at points between the nodes. In other words, an error, defined by the difference between actual values of a non-linear function and linearly interpolated values derived from the LUT, is biased.